
%------------------------------------
%
%             扩展阅读材料
%             \chapter{扩展阅读}
%------------------------------------

\section{预言机(Oracle Machine)}
Loosely speaking, an oracle machine is a machine that is augmented such that it may p ose questions to the outside. We consider the case in which these questions, called queries, are answered consistently by some function $f:\{0,1\}^* \rightarrow \{0,1\}$, called the oracle. That is, if the machine makes a query q then the answer it obtains is f (q ). In such a case, we say that the oracle machine is given access to the oracle f . For an oracle machine M , a string x and a function f , we denote by Mf(x) the output of M on input x when given access to the oracle f . (Re-examining the second part of the proof of Theorem 1.5, observe that we have actually describ ed an oracle machine that computes d' when given access to the oracle d.)\par

The notion of an oracle machine extends the notion of a standard computing device (machine), and thus a rigorous formulation of the former extends a formal model of the latter. Specifically, extending the model of Turing machines, we derive the following mo del of oracle Turing machines.\par

Definition 1.11 (using an oracle):\par
$\bullet$ An oracle machine is a Turing machine with a special additional tape, called the oracle tap e, and two special states, called oracle invocation and oracle spoke.\par

$\bullet$ The computation of the oracle machine M on input x and access to the oracle $f:\{0,1\}^* \rightarrow \{0,1\}$ is defined based on the successive configuration function.For configuration  with state different from oracle invocation the next configuration is defined as usual. Let $\gamma$ be a configuration in which the machine's state is oracle invocation and suppose that the actual contents of the oracle
tape is q (i.e., q is the contents of the maximal prefix of the tape that holds bit values).Then, the configuration following $\gamma$ is identical to $\gamma$ , except that
the state is oracle spoke, and the actual contents of the oracle tape is $f(q)$.
The string q is cal led M 's query and $f(q)$ is cal led the oracle's reply.
\par

$\bullet$ The output of the oracle machine M on input x when given oracle access to f is denote $M^f(x)$.
\par

We stress that the running time of an oracle machine is the number of steps made
during its (own) computation, and that the oracle's reply on each query is obtained
in a single step.\footnote{以上文字来自\url{https://www.wisdom.weizmann.ac.il/~oded/CC/r1.pdf}}


\section{布尔电路(Boolean Circuits)}


布尔电路模型是一个非一致性计算模型，布尔电路在开始使用时是为了描述实际电路的逻辑操作，然而，喜剧性的是，该模型现在为复杂性理论中某些与实用最无关的研究提供的研究工具。\par

\vspace{0.5cm}
A Boolean circuit is a collection of gates and wires that performs a mapping from Boolean inputs to Boolean outputs. The accepted wisdom is that such circuits must have acyclic (i.e., loop-free or feed-forward) topologies. In fact, the model is often defined this way-as a directed acyclic graph (DAG). And yet simple examples suggest that this is incorrect. We advocate that Boolean circuits should have cyclic topologies (i.e., loops or feedback paths). In other work, we demonstrated the practical implications of this view: digital circuits can be designed with fewer gates if they contain cycles. In this paper, we explore the theoretical underpinnings of the idea. We show that the complexity of implementing Boolean functions can be lower with cyclic topologies than with acyclic topologies. With examples, we show that certain Boolean functions can be implemented by cyclic circuits with as little as one-half the number of gates that are required by equivalent acyclic circuits. We also show a quadratic upper bound: given a cyclic Boolean circuit with m gates, there exists an equivalent acyclic Boolean circuit with $m^2$ gates.\footnote{文字来源\url{https://experts.umn.edu/en/publications/cyclic-boolean-circuits}}\par

\vspace{0.5cm}

An n-ary Boolean function $f(x_1,…,x_n)$ is a function from $\{0,1\}^n$ with values in $\{0,1\}$. The values 0, 1 are called Boolean values, or bits, or truth values if they are identified with false and true (cf. also Boolean function). Elements of $\{0,1\}$ are Boolean strings of length n (or bit strings). $B_n$ is the set of all $2^{2^n}$ n-ary Boolean functions.\par

A basis of connectives is any non-empty set $\Omega$ of Boolean functions, not necessarily of the same arity. An $\Omega$-formula for $f(x_1,…,x_n)$ is a formula built from Boolean variables $x_1,…,x_n$ using connectives from $\Omega$. A basis $\Omega$ is complete if all Boolean functions are definable by an $\Omega$-formula. Examples of complete bases are: $B_2$, the set of all binary Boolean functions, or the DeMorgan basis $\{0,1,\neg,\vee,\wedge\}$.\par

A more general way to \textbf{define (equivalently, compute) Boolean functions is by circuits} (straight line programs) that are simplified mathematical models of integrated circuits. A Boolean circuit over a basis $\Omega$ for $f\in B_n$ is a sequence $g_1,…,g_k$ of functions from Bn such that $g_k=f$ and such that any $g_i$ is either one of the projections $x_1,…,x_n$ or is equal to $h(g_{j_1},…,g_{j_r})$, for some $h\in \Omega$ and $j_1,…,j_r<i$. Drawing directed edges from all such $j_1,…,j_r$ to i, and labelling i by h, defines a labelled directed acyclic graph (cf. also Graph, oriented). The size of the circuit is k. The maximum length of a path from a vertex corresponding to one of the inputs $x_1,…,x_n$ to $g_k$ is the depth of the circuit. Note that formulas are circuits whose graphs are trees.\par

There are three basic ways to measure the complexity of a Boolean function, given a basis $\Omega$:

the minimum size $L_{\Omega}(f)$ of an $\Omega$-formula defining $f$,\par

the minimum size $C_{\Omega}(f)$ of a circuit over $\Omega$ defining $f$, and\par

the minimum depth $D_{\Omega}(f)$ of a circuit over $\Omega$ defining $f$. For two complete bases $\Omega$, $\Omega '$, the measures $C_{\Omega}(f)$, $C_{\Omega'}(f)$ and $D_{\Omega}(f)$, $D_{\Omega'}(f)$ are proportional to each other, and $L_{\Omega}(f)$, $L_{\Omega'}(f)$ are polynomially related. A relation exists between the formula size and the circuit depth (see [a13]): $log(L_{\Omega}(f))$ and $D_{\Omega}(f)$ are proportional to each other, provided  $\Omega$ is finite.
\par

By estimating the number of circuits of a bounded size, C.E. Shannon [a11] proved (cf. [a14] for an optimal computation) that for almost-all $f\in B_n, C_{B_2}(f)\geq 2^n/n$. On the other hand,\par

\[C_{B_2}(f) \leq \frac{2^n}{n}(1+o(1)),\]
for all $f\in B_n$, see [a8].

For a formal language $L\subseteq \{0,1\}^{∗}$, let Ln be the characteristic function of $L\cap \{0,1\}^n$. The main open problem in Boolean complexity theory (cf. [a4]) is whether there is a language L accepted by a non-deterministic polynomial-time Turing machine (cf. also Turing machine) such that $C_{\Omega}(L_n)$ is not bounded by any polynomial in n. The importance of this question stems from the fact that the affirmative answer implies that the computational complexity classes P and NP are different, as $C_{B_2}(L_n)$ is bounded by a polynomial for any L decidable in polynomial time (cf. [a10] and also NP).\par

No super-linear lower bounds on $C_{B_2}(L_n)$ are known for any $L\in NP$ However, if additional restrictions are put on the circuits, then strong lower bounds are known. Most notable are two results: any circuit of depth $d \geq 2$  over a DeMorgan-like basis $\{0,1,\neg,\vee,\wedge\}$, allowing $\vee,\wedge$ of unbounded arity, computing the parity function $\oplus_n$ must have size at least $exp(\omega(n^{1/d−1}))$ (see [a1], [a5], [a15], [a6]), and any circuit in the monotone basis $\{0,1,\vee,\wedge\}$ computing whether or not a graph on n vertices contains a clique of size at least $k\leq n^{1/4}$ must have size at least $n\omega (\sqrt{k})$ (see [a9], [a3]).\par

Interesting upper bounds are also known: a DeMorgan circuit of size  for multiplication of two n-bit long numbers, [a12] (it is still open (1998) if there are linear size circuits), and a monotone DeMorgan sorting network of simultaneous size  and depth O(logn), see [a2].\par

Various parts of computational complexity (cf. also Complexity theory) are directly related to lower-bound problems for Boolean functions; for example, communication complexity, cf. [a7].\footnote{以上文字来自\url{https://encyclopediaofmath.org/wiki/Boolean_circuit}}\par


\section{弹跳桌球(bouncing billiards ball)}
Bouncing billiards ball也是一个计算模型，下面是美国计算机协会(ACM)的一个介绍性文章“Bouncing Balls and Quantum Computing, Don Monroe
Communications of the ACM, October 2020, Vol. 63 No. 10, Pages 10-12 DOI:10.1145/3416076 ”\footnote{网址\url{https://cacm.acm.org/magazines/2020/10/247584-bouncing-balls-and-quantum-computing/fulltext}}。\par

The history of science and mathematics includes many examples of surprising parallels between seemingly unrelated fields. Sometimes these similarities drive both fields forward in profound ways, although often they are just amusing.\par

In December, Adam Brown, a physicist at Google, described a surprisingly precise relationship between a foundational quantum-computing algorithm and a whimsical method of calculating the irrational number $\pi$. "It's just a curiosity at the moment," but "the aspiration might be that if you find new ways to think about things, that people will use that to later make connections that they'd not previously been able to make," Brown said. "It's very useful to have more than one way to think about a given phenomenon."\par

In a preprint posted online (but not yet peer-reviewed at press time), Brown showed a mathematical correspondence between two seemingly unconnected problems. One is the well-known Grover search algorithm proposed for quantum computers, which should be faster than any classical equivalent. The other is a surprising procedure in which counting the number of collisions between idealized billiard balls produces an arbitrarily precise value for the $\pi$.\par

\subsection{Quantum Algorithms}
Quantum computing exploits quantum bits, or qubits, such as ions or superconducting circuits, that can simultaneously represent two distinct states. In principle, a modest number of qubits can represent and manipulate an exponentially larger number of combinations. Exploiting this possibility for computing seemed like a pipe dream, however, until researchers devised algorithms to extract useful information from the qubits. The first such algorithm, described in 1994 by Peter Shor, then at Bell Labs in New Jersey, efficiently finds the prime factors of a number, potentially cracking important cryptography schemes. The trick is to frame the problem as determining the repetition period of a sequence, essentially a Fourier transform, which can be found using global operations on an entire set of qubits.\par

The second fundamental algorithm, devised in 1996 by Lov Grover working independently at Bell Labs, operates quite differently. "Shor and Grover are the two most canonical quantum algorithms," according to Scott Aaronson of the University of Texas at Austin. "Even today, the vast majority of quantum algorithms that we know are recognizably either 'Shor-inspired' or 'Grover-inspired', or both."\par

Grover's algorithm is often described as a database search, examining a list of N items to find the item that has a desired property. If the list is ordered by some label (for example, alphabetized), any label can be found by repeatedly dividing the list in successive halves, eventually requiring log2N queries. For an unsorted list, however, checking each item in turn requires, on average N/2 steps (and possibly as many as N).\par

Like other quantum algorithms, Grover's manipulates the entire set of qubits simultaneously, while preserving the relationships between them (prematurely querying any qubit to determine its state turns it into an ordinary bit, squandering any quantum advantage). However, Grover showed the desired item can generally be found with only $\frac{\pi}{4} \sqrt{N}$ global operations.\par

This improvement is less than that seen in Shor-style algorithms, which typically are exponentially faster than their classical counterparts. The Grover approach, however, can be applied to more general, unstructured problems, Brown notes.\par

Grover's algorithm manipulates the entire set of qubits simultaneously, while preserving the relationships between them.\par

The calculation starts with an equal admixture of all N qubits. The algorithm then repeatedly subjects all the qubits to two alternating manipulations. The first operation embodies the target: it inverts the state of a specific, but unknown, bit. The task is to determine which bit is altered, but not by measuring them all. The second operation does not require any information about the target. Grover found that each time this sequence is repeated, the weight of the target in the admixture increases (although this cannot be measured). After the correct number of repetitions, there is an extremely high chance a measurement will yield the correct result.\par

\subsection{Bouncing Billiards}
These sophisticated quantum manipulations may seem to have little relationship to bouncing billiard balls. Yet Brown, while working on issues related to Grover's algorithm, came across an animation by math popularizer Grant Sanderson that made him notice the similarities. In his paper, Brown shows there is a precise mapping between the two problems.\par

Sanderson's animation illustrates a surprising observation described in 2003 by Gregory Galperin, a mathematician at Eastern Illinois University in Charleston. In the paper "Playing Pool with π," he imagined two billiard balls moving without friction along a horizontal surface, bouncing off each other and off a wall on the left side in completely elastic collisions (which preserve their combined kinetic energy).\par

If the right-hand ball is sent leftward toward a second stationary ball that is much lighter, the smaller ball will be sent back toward the left-hand wall without slowing the larger ball much. The small ball will bounce off the wall, and then collide with the large one again, repeating this multiple times. Eventually the collisions will turn the large ball around until it finally escapes to the right faster than the small ball can pursue it.\par

The number of collisions needed before this escape can occur grows larger with the ratio of the mass of the large ball compared to the small one. If the masses are equal, it will take three bounces: the first transfers all motion from the right ball to the left one, which bounces off the wall and then transfers its momentum back to the right ball again. If the large ball is 100 times as massive, the process will take 31 bounces. If the mass ratio is 10,000, there will be 314 bounces. In a spectacularly impractical computation, for every increase of a factor of 100 in the mass ratio, the number of collisions (divided by the square root the mass ratio) includes another digit to the digital representation of $\pi$, 3.141592654 …\par

Brown fortuitously encountered Sanderson's animation (which uses blocks instead of balls) when Grover's algorithm was fresh in his mind, and recognized significant similarities between the two situations. The two quantum operations, for example, correspond respectively to collisions between the balls and between the lighter ball and the wall. The mass ratio corresponds to the size of the database. Moreover, the final result was that the number of operations (or bounces) is proportional to π and to the square root of this size or mass ratio. (There are also two factors of two that reflect simple bookkeeping differences between the problems.)\par

Beyond the surprising connection between such different systems, what on earth is the number π doing in both cases? This irrational number is of course best known as the ratio of the circumference of a circle to its diameter, although it also appears in the proportions of ellipses, as well as higher-dimensional objects like spheres. One way to define a circle is through an algebraic constraint on the horizontal and vertical coordinates, x and y: The points of a circle with radius r are constrained to satisfy $x^2 + y^2 = r^2$.\par

As it turns out, both the billiard problem and the Grover algorithm have constraints of this form. Collisions of the balls or manipulations of the quantum system correspond to rotations along the circle defined by these constraints.\par

For example, for two billiards of mass m (with velocity $v_m$) and M (with velocity $v_M$), an elastic collision preserves their total kinetic energy, $\frac{1}{2} mv_M^2+\frac{1}{2} Mv_M^2$. Completely reversing the velocity of the larger ball requires a total "rotation" by 180° ($\pi$ radians) in the plane with coordinates vm and vM.\par

Similarly, for quantum systems, the probability of observing a particular outcome is proportional to the square of the "wave function" corresponding to that outcome. The sum of the probability (squared amplitude) for the target and all other outcomes must be one.\par

\subsection{Historical Examples of Connections}
There is still the question, "Is this profound insight into the nature of reality, or is it just a sort of curiosity?" Brown said. "Maybe Grover search is telling us something profound about the nature of reality, and maybe the bouncing-ball thing is more of a curiosity, and maybe connecting them is more in the spirit of the second one than the first one."\par

Still, there have been numerous cases in physics, and especially in mathematics, where such connections have contributed profoundly to progress. For example, physicists have spent more than two decades exploring a surprising correspondence between strongly interacting multi-particle quantum systems and gravitational models incorporating curved spacetime with one higher dimension. There is even hope the wormholes in spacetime can help resolve paradoxes associated with quantum-mechanical "entanglement" of distant particles.\par

For quantum systems, the probability of seeing a particular outcome is proportional to the square of the wave function corresponding to that outcome.\par

Mathematics has frequently advanced through connections between disparate fields. For example, Fermat's "last theorem," involving integer solutions of a simple equation, was only proved centuries later using methods from "elliptic curves." In another example, in January, computer scientists proved a theorem relating entanglement to Alan Turing's notion of decidable computations, which continues to shake up other seemingly unrelated fields.\par

For his part, Aaronson suspects the Grover-billiard correspondence, although "striking in its precision," is probably "just a cute metaphor (in the sense that I don't know how to use it to deduce anything about Grover's algorithm that we didn't already know). And that's fine."\par

\subsection{Further Reading}

Galperin, G.,"Playing Pool with π: The Number π from a Billiard Point of View)," Regular and Chaotic Dynamics 8, p. 375 (2003).\par

Brown, A.R.,"Playing Pool with |ψ: from Bouncing Billiards to Quantum Search," arXiv.org/abs/1912.02207 (2019).\par

Sanderson, G.,"How Pi Connects Colliding Blocks to a Quantum Search Algorithm," Quanta (2020)\par

\section{康威生命游戏(Conway's game of life)}
康威生命游戏（Conway's Game of Life），又称康威生命棋，是英国数学家约翰·何顿·康威1970年发明的细胞自动机，康威生命游戏引起了各行各业研究者的关注，这使得细胞机引起了大家的关注。约翰·何顿·康威的这篇论文发表在“Scientific American”，文章的题目为“MATHEMATICAL GAMES: The fantastic combinations of John Conway's new solitaire game "life"”\footnote{文章链接\url{https://www.ibiblio.org/lifepatterns/october1970.html}}。下面我们简单介绍一下康威生命游戏。\par
康威生命游戏，对于任意细胞，规则如下：
\begin{itemize}
	\item 每个细胞有两种状态 - 存活或死亡，每个细胞与以自身为中心的周围八格细胞产生互动（通常用图形表示时，黑色为存活，白色为死亡）
	
	\item 当前细胞为存活状态时，当周围的存活细胞低于2个时（不包含2个），该细胞变成死亡状态。（模拟生命数量稀少）
	
	\item 当前细胞为存活状态时，当周围有2个或3个存活细胞时，该细胞保持原样。
	
	\item 当前细胞为存活状态时，当周围有超过3个存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
	
	\item 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。（模拟繁殖）
\end{itemize}
可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后，可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。 \par

科学写作者王咏刚写了一篇帖子“康威生命游戏是如何搭建计算机的？”\footnote{康威生命游戏是如何搭建计算机的？，链接\url{https://zhuanlan.zhihu.com/p/144162012}}，这个文章比较完整的描述的康威生命游戏自动机理论到实践的过程。\par

\section{指针机(pointer machine)}
指针机也是一种理论计算模型，他是两种理论计算模型(计数器机和随机存取(RAM)机)的混合，而这些模型都是寄存器机(Register machine)的子类，可以证明任何正确定义的寄存器机都是图灵等价的。

\section{欧式几何、罗氏几何和黎曼几何}
古希腊大数学家欧几里德是与他的巨著《几何原本》一起名垂千古的。欧几里德把人们公认的一些事实列成定义和公理，以形式逻辑的方法，用这些定义和公理来研究各种几何图形的性质，从而建立了一套从公理、定义出发，论证命题得到定理得几何学论证方法，形成了一个严密的逻辑体系——几何学，形成了欧式几何的奠基之作。\par
在欧式几何中，代表作是“几何原本”中，有如下公理：
\begin{enumerate}
	\item 过相异两点，能作且只能作一直线。
	\item 线段(有限直线)可以任意地延长。
	\item 以任一点为圆心、任意长为半径，可作一圆。
	\item 凡是直角都相等。
	\item 两直线被第三条直线所截，如果同侧两内角和小于两个直角， 则两直线则会在该侧相交。这条公理等价于：过直线之外一点有唯一的一条直线和已知直线平行。
\end{enumerate}
在此公理上衍生出整个欧式几何。\par
俄国的尼古拉·伊万诺维奇·罗巴切夫斯基将欧式几何中的第五条公理代替为“双曲平行公理”,即“过直线之外的一点至少有两条直线和已知直线平行”，并在此公理基础上，推理出一套自洽的集合体系，我们称为罗巴切夫斯基几何(Lobachevskian geometry),罗巴切夫斯基几何从发表之处一直得不到认同,甚至得到当时学术权威的打压和嘲讽。\par

\textit{1856年2月12日，伟大的学者罗巴切夫斯基在苦闷和抑郁中走完了他生命的最后一段路程。喀山大学师生为他举行了隆重的追悼会。在追悼会上，他的许多同事和学生高度赞扬他在建设喀山大学、提高民族教育水平和培养数学人材等方面的卓越功绩，可是谁也不提他的非欧几何研究工作，因为此时，人们还普遍认为非欧几何纯属“无稽之谈”。}\par
\textit{罗巴切夫斯基为非欧几何的生存和发展奋斗了三十多年，他从来没有动摇过对新几何远大前途的坚定信念。为了扩大非欧几何的影响，争取早日取得学术界的承认，除了用俄文外，他还用法文、德文发行了自己的著作，同时还精心设计了检验大尺度空间几何特性的天文观测方案。}\par
\textit{不仅如此，他还发展了非欧几何的解析和微分部分，使之成为一个完整的、有系统的理论体系。在身患重病，卧床不起的困境下，他也没停止对非欧几何的研究。他的最后一部巨著《论几何学》，就是在他双目失明，临去世的前一年，口授他的学生完成的。}\footnote{摘自 \url{https://baike.baidu.com/item/罗巴切夫斯基几何}}\par

直到1868年，意大利数学家贝特拉米发表了一篇著名论文《非欧几何解释的尝试》，证明非欧几何可以在欧氏空间的曲面上实现。这就是说，非欧几何命题可以“翻译”成相应的欧氏几何命题，如果欧氏几何没有矛盾，非欧几何也就自然没有矛盾。直到此时，长期无人问津的非欧几何才开始获得学术界的普遍注意和深入研究，罗巴切夫斯基的独创性研究也由此得到学术界的高度评价和一致赞美，这时的罗巴切夫斯基则被人们赞誉为“几何学中的哥白尼”。
\par

黎曼几何是德国数学家黎曼创立的，他在1851年所作的一篇论文《论几何学作为基础的假设》中明确的提出另一种几何学的存在，开创了几何学的一片新的广阔领域。黎曼几何是对欧式几何第五条公理修改为：在同一平面内任何两条直线都有公共点(交点)。在黎曼几何学中不承认平行线的存在，它的另一条公设讲：直线可以无限延长，但总的长度是有限的。黎曼几何的模型是一个经过适当“改进”的球面。1845年，黎曼在哥廷根大学发表了题为《论作为几何基础的假设》的就职演讲，标志着黎曼几何的诞生。黎曼把这三种几何统一起来，统称为黎曼几何，并用这一工作，在哥廷根大学的数学系作报告，谋求一个讲师的位置。后经E．B．Christoffel，L．Bianohi及C．G．Ricci等人进一步完善和拓广，成为A．Einstein创立广义相对论(1915年)的有力数学工具。此后黎曼几何得到了蓬勃发展，特别是E．Cartan，他建立的外微分形式和活动标架法，沟通了Lie群与黎曼几何的联系，为黎曼几何的深入发展开辟了广阔的前景，影响极为深远。近半个世纪来，黎曼几何的研究从局部发展到整体，产生了许多深刻的并在其他数学分支(如代数拓扑学，偏微分方程，多复交函数论等)及现代物理学中有重要作用的结果。\par

总之，非欧几何的出现，为天体研究、现代物理、航天航空提供适用的数学工具，极大推进了相关研究工作的进展。